package com.datastructure.test.stackandsort;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

public class StackAndSort {

    public static void main(String[] args) {
        StackAndSort stackAndSort = new StackAndSort();
        int[] a= {5,2,4,3,1};
        int[] solve = stackAndSort.solve(a);
        System.out.println(solve);
    }

    public int[] solve (int[] a) {
        //记录排列的最后一位
        int n=a.length;
        //结果数组
        int[] res=new int[n];
        //新建一个栈
        LinkedList<Integer> stack=new LinkedList<>();
        int id=0;
        //dp[i]表示当前元素以及后面出现元素中的最大值
        int[] dp=new int[n];
        dp[n-1]=a[n-1];
        for(int i=n-2;i>=0;i--){
            dp[i]=Math.max(a[i],dp[i+1]);
        }
        for(int i=0;i<n;i++){
            //将当前元素入栈
            stack.push(a[i]);
            //只要栈顶元素比后面所有元素都大，则直接出栈
            while(!stack.isEmpty()&&i<n-1&&stack.peek()>dp[i+1]){
                res[id++]=stack.pop();
            }
        }
        //最后还在栈中的元素，按先进后出的顺序赋给结果数组
        while(!stack.isEmpty()){
            res[id++]=stack.pop();
        }
        return res;
    }
}
